package com.javabasic.algorithm.leetcode;

import org.checkerframework.checker.units.qual.C;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Queue;
import java.util.Set;
import java.util.TreeMap;

/**
 * @author mir.xiong
 * @version 1.0
 * @description
 * @see
 * @since Created by work on 2022/1/7 10:23 下午
 */
public class MatrixCellsInDistanceOrder {

    int[][] result;
    int rows, cols, nextLen = 4;
    int[][] next = new int[][]{{-1,0},{0,1},{1,0},{0,-1}};
    int[][] unVisit;

    /**
     * BFS+标记解法(备忘录)
     * @param rows
     * @param cols
     * @param rCenter
     * @param cCenter
     * @return
     */
    public int[][] allCellsDistOrder2(int rows, int cols, int rCenter, int cCenter) {
        result = new int[rows*cols][2];
        unVisit = new int[rows][cols];
        this.rows = rows;
        this.cols = cols;

        bfs(rCenter,cCenter);

        return result;
    }

    private void bfs(int rCenter, int cCenter) {
        int index = 0;
        result[index][0] = rCenter;
        result[index][1] = cCenter;
        index++;

        BfsNode bfsNode = new BfsNode(rCenter, cCenter);
        unVisit[rCenter][cCenter] = 1;
        Queue<BfsNode> bfsNodesQueue = new LinkedList<>();
        bfsNodesQueue.offer(bfsNode);
        int tempx, tempy;

        while (!bfsNodesQueue.isEmpty()) {
            BfsNode currentNode = bfsNodesQueue.poll();
            for (int i = 0; i < nextLen; i++) {
                tempx = currentNode.rCenter+next[i][0];
                tempy = currentNode.cCenter+next[i][1];
                if (!validCoordinate(tempx,tempy)) {
                    continue;
                }
                unVisit[tempx][tempy] = 1;
                result[index][0] = tempx;
                result[index][1] = tempy;
                index++;
                bfsNode = new BfsNode(tempx,tempy);
                bfsNodesQueue.offer(bfsNode);
            }
        }
    }

    private boolean validCoordinate(int rCenter, int cCenter) {
        if (rCenter < 0 || rCenter >= this.rows || cCenter < 0 || cCenter >= this.cols || unVisit[rCenter][cCenter] == 1) {
            return false;
        }
        return true;
    }

    class BfsNode {
        private int rCenter;
        private int cCenter;

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            BfsNode bfsNode = (BfsNode) o;
            return rCenter == bfsNode.rCenter && cCenter == bfsNode.cCenter;
        }

        @Override
        public int hashCode() {
            return Objects.hash(rCenter, cCenter);
        }

        public BfsNode(int rCenter, int cCenter) {
            this.rCenter = rCenter;
            this.cCenter = cCenter;
        }
    }

    /**
     * 暴力解法，Map+思维逻辑
     * @param rows
     * @param cols
     * @param rCenter
     * @param cCenter
     * @return
     */
    public int[][] allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {
        Map<Integer, List<Coordinates>> distancesToCoordinate = new TreeMap<>();
        int distance = 0;
        List<Coordinates> orDefault;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                distance = Math.abs(rCenter-i) + Math.abs(cCenter-j);
                orDefault = distancesToCoordinate.getOrDefault(distance, new ArrayList<>());
                orDefault.add(new Coordinates(i,j));
                distancesToCoordinate.put(distance,orDefault);
            }
        }

        int[][] result = new int[rows*cols][2];
        int index = 0;
        Set<Map.Entry<Integer, List<Coordinates>>> entrySet = distancesToCoordinate.entrySet();
        for (Map.Entry<Integer, List<Coordinates>> entry : entrySet) {
            List<Coordinates> value = entry.getValue();
            if (value.isEmpty()) {
                continue;
            }
            for (Coordinates coordinates : value) {
                result[index][0] = coordinates.x;
                result[index][1] = coordinates.y;
                index++;
            }
        }

        return result;
    }

    class Coordinates {
        int x;
        int y;

        public Coordinates(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Coordinates that = (Coordinates) o;
            return x == that.x && y == that.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }
    }
}
